/*
 *  Copyright (C) 2010 Matthias Buch-Kromann <mbk.isv@cbs.dk>
 * 
 *  This file is part of the IncrementalParser package.
 *  
 *  The IncrementalParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package org.osdtsystem.incparser.parsers;

import org.osdtsystem.incparser.features.FeatureHandler;
import org.osdtsystem.incparser.features.WeightVector;
import org.osdtsystem.incparser.graphs.BaseGraph;
import org.osdtsystem.incparser.graphs.ConllAdapter;
import org.osdtsystem.incparser.graphs.GraphOverlayAddEdge;
import org.osdtsystem.incparser.graphs.GraphOverlayMoveEdge;
import org.osdtsystem.incparser.graphs.LocalGraph;

/**
 *
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public abstract class AbstractIncrementalConllParser extends AbstractConllParser {
    public AbstractIncrementalConllParser(FeatureHandler edgeTypeHandler,
            FeatureHandler stringHandler, FeatureHandler featureHandler) {
        super(edgeTypeHandler, stringHandler, featureHandler);
    }

    @Override
    public ConllAdapter parse( WeightVector weights, ConllAdapter adapter) {
        // Remove edges from graph and compute number of nodes and edge types
        adapter.clearEdges();
        BaseGraph graph = adapter.baseGraph();
        int nodes = adapter.nodes(graph);

        // Process nodes incrementally from left to right
        for (int node = 1; node < nodes; node++) {
            // First attach to the best possible left head
            attachToBestLeft(adapter, node);

            // Now try to see if any of the nodes to the left want to attach to the right
            for (int left = node - 1; left > 0; --left) {
                if (! adapter.dominates(graph, left, node)) {
                    // Dependent does not dominate newhead, so we can attach directly
                    _tryAttachToRightDirect(adapter, left, node);
                } else {
                    // Dependent dominates node, so we nead to break cycle before reattaching
                    _tryAttachToRightBreakCycle(adapter, left, node);
                }
            }
        }

        // Return parse
        return adapter;
    }

    void attachToBestLeft(ConllAdapter adapter, int node) {
        // Extract base graph and types
        BaseGraph graph = adapter.baseGraph();
        int layer = adapter.layer();
        int types = edgeTypeHandler.features();
        
        // Create initial overlay
        GraphOverlayAddEdge overlay = null;

        //  Find best head to the left
        double bestscore = Double.NEGATIVE_INFINITY;
        int besthead = 0;
        int besttype = 0;
        for (int head = node - 1; head >= 0; --head) {
            // Set new edge in overlay
            if (overlay == null)
                overlay = graph.makeOverlayAddEdge(layer, node, head, 0);
            else
                overlay.setEdge(node, head, 0);

            // Set best edge type
            overlay.setBestEdgeType(types);

            // Calculate score and update best
            double score = overlay.score();
            if (score > bestscore) {
                bestscore = score;
                besthead = head;
                besttype = overlay.edgeType();
            }
        }

        // Write best attachment to base graph
        overlay.setEdge(node, besthead, besttype);
        overlay.writeToBaseGraph();
    }

    void _tryAttachToRightDirect(ConllAdapter adapter, int left, int node) {
        // Find base graph and old head
        BaseGraph graph = adapter.baseGraph();
        int layer = adapter.layer();
        LocalGraph localGraph = adapter.localGraph(graph, left);
        int oldhead = localGraph.headNode();
        int oldtype = localGraph.headType();
        int types = edgeTypeHandler.features();

        // Create overlay by attaching left to node with the best possible edge type
        GraphOverlayMoveEdge overlay = graph.makeOverlayMoveEdge(layer, left, oldhead, oldtype, node, 0);
        overlay.setBestEdgeType(types);

        // Attach right if best overlay score is better than original score
        if (overlay.score() > graph.score())
            overlay.writeToBaseGraph();
    }



    void _tryAttachToRightBreakCycle(ConllAdapter adapter, int left, int node) {
        // Oops! node dominates newhead so direct attachment would result in a cycle.
        // Try to see if we can reattach any of the nodes from newhead and up to
        // (and excluding) node to a head that isn't dominated by node,
        // at a lower cost than the potential gain from reattaching node
        // to head

        // Find base graph and old head
        BaseGraph graph = adapter.baseGraph();
        int layer = adapter.layer();
        LocalGraph localGraph = adapter.localGraph(graph, left);
        int oldhead = localGraph.headNode();
        int oldtype = localGraph.headType();
        int types = edgeTypeHandler.features();

        // Create first overlay where left attaches to node with highest-scoring edge type
        GraphOverlayMoveEdge overlay1 = graph.makeOverlayMoveEdge(layer, left, oldhead, oldtype, node, 0);
        overlay1.setBestEdgeType(types);

        // Create second overlay where some node from node and up to and excluding
        // left attaches to a node not dominated by left in the original graph
        double bestScore = Double.NEGATIVE_INFINITY;
        int bestPnode = 0;
        int bestPhead = 0;
        int bestPtype = 0;
        int bestOldPhead = 0;
        int bestOldPtype = 0;
        GraphOverlayMoveEdge overlay2 = null;

        // Iterate over all possible new pnode heads (those not dominated by left in the original graph)
        for (int phead = 0; phead < graph.nodes(); ++phead) {
            // Skip nodes that are dominated by left in the original graph
            if (adapter.dominates(graph, left, phead))
                continue;

            // Examine all nodes on the upwards path from node (inclusive) to
            // left (non-inclusive)
            int pnode = node;
            while (pnode != left) {
                // Get local graph for pnode
                LocalGraph pnodeLocalGraph = graph.localGraph(pnode, layer);
                int oldPhead = pnodeLocalGraph.headNode();
                int oldPtype = pnodeLocalGraph.headType();

                // Create overlay and set edge type to best
                if (overlay2 == null)
                    overlay2 = graph.makeOverlayMoveEdge(layer, pnode, oldPhead, oldPtype, phead, 0);
                else
                    overlay2.setMoveEdge(pnode, oldPhead, oldPtype, phead, 0);
                overlay2.setBestEdgeType(types);

                // Update best scoring change
                double overlay2Score = overlay2.score();
                if (overlay2Score > bestScore) {
                    bestScore = overlay2Score;
                    bestPnode = pnode;
                    bestPhead = phead;
                    bestPtype = overlay2.edgeType();
                    bestOldPhead = oldPhead;
                    bestOldPtype = oldPtype;
                }

                // Move upwards in the path
                pnode = graph.localGraph(pnode, layer).headNode();
            }
        }

        // Write overlays to graph if better than original score
        if (bestScore > graph.score()) {
            overlay2.setMoveEdge(bestPnode, bestOldPhead, bestOldPtype, bestPhead, bestPtype);
            overlay2.writeToBaseGraph();
        }
    }
}
